package com.zh.note.huawei.onehundred.完全二叉树非叶子部分后序遍历;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * https://dream.blog.csdn.net/article/details/131754726
 */
public class Main {
    public static void main(String[] args) {
        // Scanner sc = new Scanner(System.in);
        // String input = sc.nextLine();
        String input = "1 2 3 4 5 6 7 8 9";
        int[] nums = Arrays.stream(input.split(" ")).mapToInt(Integer::parseInt).toArray();
        String res = solution(nums);
        System.out.println(res);
    }

    private static String solution(int[] nums) {

        if (nums.length == 1) {
            return Integer.toString(nums[0]);
        }
        List<Integer> list = new ArrayList<>();
        dfs(nums, 0, list);
        return list.stream().map(String::valueOf).collect(Collectors.joining(" "));
        // StringBuilder sb = new StringBuilder();
        // for (int i = 0; i < list.size(); i++) {
        //     sb.append(list.get(i)).append(" ");
        // }
        // return sb.toString().trim();
    }

    //depth代表层数，从第0层开始
    private static void dfs(int[] nums, int depth, List<Integer> res) {
        int left = depth * 2 + 1;
        int right = depth * 2 + 2;
        if (left < nums.length) {
            dfs(nums, left, res); //左
            if (right < nums.length) {
                dfs(nums, right, res);//右
            }
            res.add(nums[depth]);//中
        }
    }
}
